package com.fosss.dijkstra;

public class Graph {
    private char[] vertexs;//顶点数组
    private int[][] matrix;//邻接矩阵
    VisitedVertex vv;

    public Graph(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
    }

    /**
     * 打印邻接矩阵
     */
    public void print(){
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.printf("%-12d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 编写算法
     * @param index 出发d顶点的下标
     */
    public void dijkstraGo(int index){
        vv = new VisitedVertex(vertexs.length, index);
        //更新该顶点到其他顶点的距离和前驱顶点
        update(index);
        //更新其他顶点
        for(int i=1;i<vertexs.length; i++){
            int newIndex = vv.updateArr();//获取新的访问顶点
            update(newIndex);//进行更新
        }

    }

    /**
     * 更新index顶点到其他顶点的距离和前驱顶点
     */
    public void update(int index){
        for(int i=0;i<matrix[index].length;i++){
            //i顶点未被访问过，并且出发顶点到index顶点的距离加上index顶点到i顶点的距离比出发顶点到i顶点的距离小的话，就更新
            int len=(vv.distance[index]+matrix[index][i]);
            if(!vv.visited[i]&&len<vv.distance[i]){
                //设置出发顶点到i顶点的距离
                vv.distance[i]=len;
                //设置i顶点的前驱顶点
                vv.pre[i]=index;
            }
        }
    }

    /**
     * 打印
     */
    public void show(){
        vv.show();
    }


}














